package com.suanfa.dp;

/**
 * 最长回文子串
 */
public class Palindrome {

    /**
     * 动态规划 dp[i][j] = dp[i+1][j-1] && s[i] == s[j]
     * i == j  dp[i][j] = true;
     * j-i == 1  dp[i][j] =s[i]==s[j]
     * @param s
     * @return
     */
    public static String longestPalindrome2(String  s){
        if(s.length() <2){
            return s;
        }

        int start = 0;
        int max = 1;
        char[] ch = s.toCharArray();
        boolean[][] dp = new boolean[s.length()][s.length()];
        for(int i =0; i< s.length(); i++){
            dp[i][i] = true;
        }
        for(int i=1; i< s.length(); i++){
            for(int j=0; j< i; j++){
                if(ch[j] != ch[i]){
                    dp[j][i] = false;
                    continue;
                }else {
                    if(i-j < 3){  //aba  aa
                        dp[j][i]=true;
                    }else{
                        dp[j][i] = dp[j+1][i-1];
                    }
                }
                int length = i-j+1;
                if(dp[j][i] && max < length){
                    max = length;
                    start = j;
                }

            }
        }
        return s.substring(start, start+max);


    }





    /**
     * 构造每个子串，判断子串是不是回文 容易超时
     */

    public static String  longestPalindrome(String s){

        if(s.length() < 2){
            return s;
        }
        int start = 0;
        int max = 0;
        for(int i = 0; i< s.length()-1; i++){
            for(int j = i+1; j <s.length(); j++){
                int length = j-i+1;
                if(length > max && isPalindrome(s,i,j)){
                    start = i;
                    max = length;
                }

            }

        }
        return s.substring(start, start+ max);

    }

    public static boolean isPalindrome(String s, int left, int right){
        char[] ch = s.toCharArray();

        while(left<right){

            if(ch[left] != ch[right]){
               return false;
            }
            left++;
            right--;
        }
        return true;


    }
}
